
import random
import time

"""
冒泡排序
相邻元素进行比较 如果符合我的预期(小-大)  不符合交换元素
"""
# list = [3, 2, 5, 1, 10,  5, 7, 2, 1, 9, 6]
#
# for i in range(len(list)-1):
#     for j in range(len(list)-i-1):
#         if list[2] > list[1]:
#             """
#                 3, 2, 5, 1, 10, 5, 7, 2, 1, 9, 6
#                 一
#                 2, 3, 1, 5, 5, 7, 2, 1, 9, 6, 10
#
#                 2, 1, 3, 5, 5, 2, 1, 7, 6, 9, 10
#                 1, 2, 3, 5, 2, 1, 5, 6, 7, 9, 10
#                 1, 2, 3, 2, 1, 5, 5, 6, 7, 9, 10
#                 1, 2, 2, 1, 3, 5, 5, 6, 7, 9, 10
#                 1, 2, 1, 2, 3, 5, 5, 6, 7, 9, 10
#                 1, 1, 2, 2, 3, 5, 5, 6, 7, 9, 10
#             """
#             list[j], list[j+1] = list[j+1], list[j]
#
#     print(list)


"""
选择排序
"""
# A = [12, 22, 15, 1, 8]
#
# def select(lst):
#     for i in range(len(lst)-1):
#         min_ = i
#         for j in range(i+1, len(lst)):
#
#             if lst[j] < lst[min_]:
#                 min_ = j
#         lst[min_], lst[i] = lst[i], lst[min_]
#         print(lst)
#     return lst
#
#
# B = select(A)

# print(B)


"""
插入排序
"""
# def inst(arr):
#     # 第一层for表示循环插入的遍数
#     for i in range(1, len(arr)):
#         # 当前需要插入的元素
#         current = arr[i]
#         # 与当前元素比较的元素
#         pre = i - 1
#
#         while pre >= 0 and arr[pre] > current:
#
#             # 当比较元素大于当前元素则把比较元素后移
#             arr[pre + 1] = arr[pre]
#
#             # 往前选择下一个元素
#             pre -= 1
#         # 当比较元素小于当前元素， 则把当前元素插入在其后面
#         arr[pre + 1] = current
#     return arr
#
# A = [11, 32, 23, 22, 66, 88, 99,11]
# B = inst(A)
# print(B)


"""
快速排序
"""

# def quick(alist):
#
#     if not alist:
#         return alist
#
#     pivot = random.choice(alist)
#     print(pivot)
#
#     # 存放和中间数一样的值
#     equaList = []
#     # 存放比中间数小的值
#     smallList = []
#     # 存放比中间数大的值
#     biggerList = []
#
#     for i in alist:
#         if i < pivot:
#             smallList.append(i)
#         elif i == pivot:
#             equaList.append(i)
#         else:
#             biggerList.append(i)
#     return quick(biggerList) + equaList + quick(smallList)
#
# a = [3, 1, 8,9, 2, 6, 0]
# su = quick(a)
# print(su)

# list = []
# for i in range(0, 10000):
#     list.append(random.randint(1, 1000))
#
# print(list)
#
#
# # 冒泡排序
# items = time.time()
# for i in range(len(list) - 1):
#     for j in range(len(list) - i - 1):
#         if list[j] > list[j + 1]:
#             list[j], list[j + 1] = list[j + 1], list[j]
# item = time.time()
# print('冒泡排序耗费的时间', item-items)
# print(list)
#
#
# # 选择排序
# time1 = time.time()
# def select(list):
#     for i in range(len(list)-1):
#         min_ = i
#         for j in range(i+1,len(list)):
#
#             if list[j] < list[min_]:
#                 min_ = j
#         list[min_], list[i] = list[i], list[min_]
#     return list
# a = select(list)
# time2 = time.time()
# print('选择排序耗费的时间', time2-time1)
# print(a)
#
#
# # 插入排序
# time3 = time.time()
# def inst(arr):
#     for i in range(1, len(arr)):
#         current = arr[i]
#
#         pre = i - 1
#         while pre >= 0 and arr[pre] > current:
#
#             arr[pre + 1] = arr[pre]
#
#             pre -= 1
#         arr[pre + 1] = current
#     return arr
# a = inst(list)
# time4 = time.time()
# print('插入排序耗费的时间', time4-time3)
# print(a)
#
# # 快速排序
# times = time.time()
# def quick(alist):
#     if not alist:
#         return alist
#
#     pivot = random.choice(alist)
#     # print(pivot)
#
#     # 存放和中间数一样的值
#     equaList = []
#     # 存放比中间数小的值
#     smallList = []
#     # 存放比中间数大的值
#     biggerList = []
#
#     for i in alist:
#         if i < pivot:
#             smallList.append(i)
#         elif i == pivot:
#             equaList.append(i)
#         else:
#             biggerList.append(i)
#     return quick(smallList) + equaList + quick(biggerList)
# su = quick(list)
# timess = time.time()
# print('快速排序的时间',timess-times)
# print(su)
#
#
# #  希尔排序
# def shell(arr):
#     # 取整计算增量(间隔)值
#     gap = len(arr) // 2
#     while gap > 0:
#         # 从增量开始遍历比较
#         for i in range(gap, len(arr)):
#             j = i
#             current = arr[i]
#             # 元素于他同列的前面的每个元素比较，如果比前面的小则交换 其实就是插入排序
#             while j - gap >= 0 and current < arr[j - gap]:
#                 arr[j] = arr[j - gap]
#                 j -= gap
#             arr[j] = current
#         # 缩小增量(间隔)值
#         gap //= 2
#     return arr
# sort = shell([3,1,8,9,2,6,0,8])
# print(sort)


# 计数排序


def counting_sort(array):
    # 获取最大值 最小值
    largest = max(array)
    smsllest = min(array)

    # 用于统计个数的一个空数组
    counter = [0 for i in range(largest-smsllest+1)]

    # 桶内索引值
    idx = 0

    for i in range(len(array)):
        # 统计每个元素出现的次数
        counter[array[i]-smsllest] += 1

    for j in range(len(counter)):
        while counter[j] > 0:
            # 取出元素
            array[idx] = j + smsllest
            idx += 1
            counter[j] -= 1
    return array

a = [5,2,8,9,1,2]

counting_sort(a)
print(a)

